\section{Performance Analysis}
\label{sec:performance}

Due to the speed of the GMP library, it was necessary to run the tests on very large numbers, that is over one million digits or more. Our tests frequently used numbers in the tens or hundreds of millions digits. Because of the size of these numbers, it takes considerably more time to generate the numbers than is does to perform the operations on them. To generate the numbers, the \ttt{mpz\_urandomm()} function is used. Please realize that if you rerun the tests, the time it takes to complete will be much larger than the operation times because of the random number. There is also additional overhead from running each operation 20 times and then taking the minimum value. This is possible since the data we are gathering cannot be understimated so running multiple trials hopefully prevents outside factors from affecting our final results.\\

There were two different areas of focus for the multiplication performance. The first, of course was how the system performed for very large numbers. The range was chosen so that the times for \ttt{mpz\_mul()} were greater than 0. The second was the performance around the thresholds. We wanted to get some sense of how the system was performing around these thresholds and how the different algorithms affected cycle count, instruction count, and cache misses. To investigate the threshold performance, scales of numbers were used such that they crossed the threshold during the test. There were three thresholds that were investigated and monitored using PAPI. No timings were gathered since the operations ran in an unmeasurable time interval.

\subsection{Addition}
\label{ssec:addition}
Since there are not different algorithms used for addition, we did not need to worry about threshold values and their effect on the operations. Our tests collected and recorded the following data for each test,

\bullets {
	\item Number of digits
	\item Number of limbs
	\item Total instructions(PAPI)
	\item Total cycles(PAPI)
	\item L1 data cache misses(PAPI)
	\item L2 data cache misses(PAPI)
	\item Time in seconds
}

Each addend was generated to be the same number of digits which also guarenteed that they would be the same number of limbs. Integers from 10 million to 410 million digits were used as addends with a step size of 20 million digits giving 20 results.

\clearpage

\subsubsection{Raw Data}
Below is the raw data gathered during our testing of integer addition.\\

\begin{table}[h!]
\caption{Performance of mpz\_add()}
\centering
\begin{tabular}{ccccccc}
\hline\hline
Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM & Time(s)\\
\hline
10000000&519052&3114675&12420788&194682&68928&0\\
30000000&1557154&9343305&31853459&583979&203683&0.01\\
50000000&2595257&15571923&52881345&973278&311426&0.02\\
70000000&3633359&21800540&70503638&1362573&410995&0.03\\
90000000&4671462&28029169&114465743&1751901&547342&0.06\\
110000000&5709564&34257785&139385241&2141201&660982&0.07\\
130000000&6747667&40486412&169436362&2530519&873990&0.09\\
150000000&7785769&46715010&157499346&2808543&1024995&0.08\\
170000000&8823872&52943655&224273396&3309129&1290422&0.12\\
190000000&9861975&59172275&238344190&3695066&1275609&0.13\\
210000000&10900077&65400890&265252953&4087729&1397094&0.14\\
230000000&11938180&71629493&246563451&4458146&1561205&0.13\\
250000000&12976282&77858112&285995023&4866276&1768416&0.16\\
270000000&14014385&84086731&297947395&5215292&1816044&0.16\\
290000000&15052487&90315384&337673045&5640000&1249309&0.19\\
310000000&16090590&96543987&403008952&6031785&1254973&0.22\\
330000000&17128692&102772606&429520242&6421092&1340267&0.24\\
350000000&18166795&109001232&456801304&6810467&1421332&0.25\\
370000000&19204897&115229848&483314023&7199044&1506141&0.26\\
390000000&20243000&121458466&509808296&7590679&1591551&0.27\\
\hline
\end{tabular}
\label{table:mpz_add}
\end{table}

\clearpage

\subsubsection{Digits vs. Limbs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_limbs.png}
\end{figure}
\subsubsection{Limbs vs. Instructions Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_instructions.png}
\end{figure}
\subsubsection{Limbs vs. Cycles Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_cycles.png}
\end{figure}
\subsubsection{Limbs vs. L1 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_l1_dcm.png}
\end{figure}
\subsubsection{Limbs vs. L2 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_l2_dcm.png}
\end{figure}
\subsubsection{Limbs vs. Time Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{add_time.png}
\end{figure}

\subsection{Large Integer Multiplication}
\label{ssec:multiplication}
Like the addition performance tests, the multiplication tests collected and recorded the following data:

\bullets {
	\item Number of digits
	\item Number of limbs
	\item Total instructions(PAPI)
	\item Total cycles(PAPI)
	\item L1 data cache misses(PAPI)
	\item L2 data cache misses(PAPI)
	\item Time in seconds
}

Both the multiplier and the multiplicand were generated to be the same number of digits which also guarenteed that they would be the same number of limbs. Integers from 10 million to 41 million digits were used as addends with a step size of 2 million digits giving 20 results.

\subsubsection{Thresholds}
\label{sssec:thresholds}
As discussed in \S \ref{ssec:algorithms}, the GMP library implements 4 algorithms for integer multiplication. The library determines which algorithm to use based on certain thresholds, namely:

\bullets{
	\item MUL\_KARATSUBA\_THRESHOLD
	\item MUL\_TOOM3\_THRESHOLD
	\item MUL\_FFT\_THRESHOLD
}

When the multiplication function \ttt{mpn\_mul()}, multi-precision number multiplication, is called, it uses these thresholds and the size of the numbers to determine the optimal algorithm. The size of the number and the thresholds are both represented as the number of limbs. A limb is the smallest part of a multi-precision number that fits into a single word. This value is stored in \ttt{gmp-mparam.h} and can also be found using \ttt{cout << sizeof(mp\_limb\_t)}. On \ttt{tux64-03.cs.drexel.edu}, the word size if 64 bits so the limb size is also 64 bits. This means that each limb can store numbers up to $2^64$ or $18446744073709551616$. As we can see, each limb can store every 19 digits number and can even store some 20 digits numbers. The threshold values determined by running \ttt{make} were:

\bullets{
	\item MUL\_KARATSUBA\_THRESHOLD = 31
	\item MUL\_TOOM3\_THRESHOLD = 105
	\item MUL\_FFT\_THRESHOLD = 4736
}

GMP also provides a tuning program that attempts to find the best threshold values for a given machine. The tuning program estimated the following to be the optimal settings for the thresholds:

\bullets{
	\item MUL\_KARATSUBA\_THRESHOLD = 32
	\item MUL\_TOOM3\_THRESHOLD = 105
	\item MUL\_FFT\_THRESHOLD = 3712
}

As we can see, the only major difference is in the FFT threshold value. The difference in the Karatsuba threshold is trivial because it only equates to a difference of 20 digits, which is a trivial amount for GMP. While the difference in FFT thresholds was large, over 1000, it was not changed in \ttt{gmp-mparam.h}. The reasoning behind this is that even million digit numbers can be multiplied in ``0.0'' seconds so the change would not have effected anything since the difference only represents a little over 19000 digits.

\clearpage

\subsubsection{Raw Data}
Below is a table containing the raw data for the large number multiplication test:
\begin{table}[h!]
\caption{Performance of mpz\_mul()}
\centering
\begin{tabular}{ccccccc}
\hline\hline
Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM & Time(s)\\
\hline
1000000&51906&261498331&170597905&898928&335538&0.09\\
3000000&155716&859016747&599195719&2827366&1550409&0.33\\
5000000&259526&1782446873&1180892420&5103760&3057592&0.65\\
7000000&363336&2794878390&1755146686&7141708&4442197&0.97\\
9000000&467147&3377123614&2340735509&11345685&6464459&1.3\\
11000000&570957&4578335293&3039064246&14390154&8367755&1.7\\
13000000&674767&5963633580&3891119823&18210364&10785654&2.16\\
15000000&778577&6739293261&4147220039&20282261&9813210&2.33\\
17000000&882388&7165035593&4779309353&22240031&10738858&2.68\\
19000000&986198&8517356187&5544294822&26323941&13433642&3.11\\
21000000&1090008&9154459734&6170050969&27861709&17293747&3.46\\
23000000&1193818&9930343657&6326038069&30578638&15797742&3.57\\
25000000&1297629&10532895160&6680611513&32806431&16915095&3.78\\
27000000&1401439&11039017292&7389728401&34578361&18809525&4.18\\
29000000&1505249&12287390167&8114345217&38230665&21117995&4.6\\
31000000&1609059&12791957866&8539857254&41011290&20439815&4.83\\
33000000&1712870&15057930789&9363347950&50219842&22274665&5.29\\
35000000&1816680&15786572457&10619992782&55546419&25961837&6.01\\
37000000&1920490&15790297291&10648185669&57052883&27791537&6.02\\
39000000&2024300&18948675651&12336267010&64723194&31506660&6.97\\
\hline
\end{tabular}
\label{table:mpz_mul}
\end{table}

\clearpage

\subsubsection{Digits vs. Limbs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_limbs.png}
\end{figure}
\subsubsection{Limbs vs. Instructions Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_instructions.png}
\end{figure}
\subsubsection{Limbs vs. Cycles Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_cycles.png}
\end{figure}
\subsubsection{Limbs vs. L1 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_l1_dcm.png}
\end{figure}
\subsubsection{Limbs vs. L2 DCMs Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_l2_dcm.png}
\end{figure}
\subsubsection{Limbs vs. Time Graph}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{mul_time.png}
\end{figure}

\subsection{Threshold Multiplication}
\label{ssec:threshold_mul}
To gather performance data around the threshold values, the size of the test numbers must be determined. \S \ref{sssec:thresholds} showed that each limb can hold a number in the low 20 digit range. Assuming that the thresholds are the same as that in \S \ref{sssec:thresholds} then the following number ranges would be reasonable test bounds for the multiplication thresholds.\\

\begin{center}
 \begin{tabular}{|c|c|c|c|c|}
	\hline
	\bf Threshold & \bf Limbs & \bf Approx. Digits & \bf Lower Digit Bound & \bf Upper Digit Bound\\
	\hline
	Karatsuba & 31 & 593.817567568 & 589 & 620\\
	\hline
	Toom3 & 105 & 2011.317567568 & 1995 & 2100\\
	\hline
	FFT & 4736 & 90720 & 89984 & 94720\\
	\hline
 \end{tabular}
\end{center}

The lower bound assumes every limb generated is 19 digits while the upper bound assumes that every limb generated is 20 digits. The Approx. Digits field tries to estimate the average number of digits for a number by using that fact that a limb can store every 19 digit number but only about $0.184$ of possible 20 digit numbers. Since all our generated limbs will be either 19 or 20 digits, the overall length will be $\frac{1}{1.184} * 19 * L + \frac{0.184}{1.184} * 20 * L$ where $L$ is the number of limbs.\\

By testing integers in the ranges defined by the lower and upper bounds in the table above, the performance of the different algorithms could be compared. To generate integers for this portion of the testing a new number generator was used. The previous one generated numbers to an approximate number of digits. The code below generates numbers to an exact number of digits, thus giving complete control to the integers generated to test the thresholds. This string result can be used to generate \ttt{mpz\_t} values by using \ttt{mpz\_set\_str()} or \ttt{mpz\_init\_set\_str()}.

\lstinputlisting[frame=single,numbers=left,showstringspaces=false,language={C++},caption={generator.cpp},label={code:generator}]{../src/generator.cpp}

\subsubsection{Raw Data}
\bullets {
	\item Karatsuba's
\begin{table}[h!]
\caption{Performance around MUL\_KARATSUBA\_THRESHOLD}
\centering
\begin{tabular}{cccccc}
\hline\hline
Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM\\
\hline
550&29&9355&4800&5&2\\
555&29&9355&4800&5&2\\
560&30&9962&5032&5&2\\
565&30&9962&5032&5&2\\
570&30&9962&5032&5&2\\
\bf 575&\bf 30&\bf 9962&\bf 5032&\bf 5&\bf 2\\
\bf 580&\bf 31&\bf 9597&\bf 5637&\bf 16&\bf 2\\
585&31&9597&5640&16&2\\
590&31&9597&5640&16&2\\
595&31&9597&5640&16&2\\
600&32&9967&5762&16&2\\
605&32&9967&5762&16&2\\
610&32&9967&5762&16&2\\
615&32&9967&5762&16&2\\
620&33&10666&6135&17&2\\
625&33&10666&6132&17&2\\
630&33&10666&6135&17&2\\
635&33&10666&6135&17&2\\
640&34&11056&6224&18&2\\
645&34&11056&6224&18&2\\
\hline
\end{tabular}
\label{table:tmul_karatsuba}
\end{table}

	\item Toom 3
\begin{table}[h!]
\caption{Performance around MUL\_TOOM3\_THRESHOLD}
\centering
\begin{tabular}{cccccc}
\hline\hline
Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM\\
\hline
1900&99&66863&32344&4&4\\
1915&100&67463&32588&4&4\\
1930&101&69587&33402&8&4\\
1945&101&69587&33402&8&4\\
1960&102&70692&33892&15&4\\
1975&103&71827&34291&8&4\\
\bf 1990&\bf 104&\bf 72449&\bf 34544&\bf 8&\bf 4\\
\bf 2005&\bf 105&\bf 70077&\bf 35650&\bf 16&\bf 4\\
2020&105&70086&35703&16&4\\
2035&106&72376&36961&16&4\\
2050&107&73153&37166&15&4\\
2065&108&73553&37276&15&4\\
2080&108&73548&37326&15&4\\
2095&109&75495&38351&21&0\\
2110&110&75924&38424&21&4\\
2125&111&76695&38798&21&4\\
2140&112&79100&40129&21&4\\
2155&112&79094&40075&21&4\\
2170&113&79905&40386&21&4\\
2185&114&80320&40571&20&4\\
\hline
\end{tabular}
\label{table:tmul_toom3}
\end{table}

	\item FFT
\begin{table}[h!]
\caption{Performance around MUL\_FFT\_THRESHOLD}
\centering
\begin{tabular}{cccccc}
\hline\hline
Digits & Limbs & Instructions & Cycles & L1 DCM & L2 DCM\\
\hline
85000&4412&21083488&10123361&18800&0\\
85500&4438&21387829&10235777&18707&0\\
86000&4464&21616311&10338655&20259&8\\
86500&4490&21771854&10410464&19839&2\\
87000&4516&22013472&10504041&19096&3\\
87500&4542&22180144&10591606&21121&2\\
88000&4568&22348946&10669201&21226&1\\
88500&4594&22655580&10787793&20852&5\\
89000&4620&22872480&10868614&20542&1\\
89500&4646&23046203&10933816&20796&1\\
90000&4672&23298978&11038190&21037&1\\
90500&4698&23473149&11111002&21163&0\\
\bf 91000&\bf 4724&\bf 23640447&\bf 11183028&\bf 21362&\bf 0\\
\bf 91500&\bf 4750&\bf 18037297&\bf 9927196&\bf 47510&\bf 0\\
92000&4776&18039146&9933301&47613&3\\
92500&4802&19938101&10671776&44245&0\\
93000&4828&19925875&10665118&44277&0\\
93500&4854&19942408&10677762&44234&0\\
94000&4880&19931808&10663479&44224&1\\
94500&4906&19938770&10669051&44175&0\\
\hline
\end{tabular}
\label{table:tmul_fft}
\end{table}
}

\subsubsection{Graphs}
\bullets{
	\item Karatsuba's
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_karatsuba_limbs.png}
\end{figure}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_karatsuba_counts.png}
\end{figure}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_karatsuba_dcm.png}
\end{figure}

	\item Toom 3
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_toom3_limbs.png}
\end{figure}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_toom3_counts.png}
\end{figure}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_toom3_dcm.png}
\end{figure}

	\item FFT
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_fft_limbs.png}
\end{figure}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_fft_counts.png}
\end{figure}
\begin{figure}[H]
  \centering
    \includegraphics[width=0.8\textwidth]{tmul_fft_dcm.png}
\end{figure}
}